package www.study.com;

import java.util.HashMap;
import java.util.Map;

//两数之和 https://leetcode.cn/problems/two-sum/
public class code1 {
    public static void main(String[] args) {

    }
    class Solution{
        //方式一：时间复杂度0(n^2)
        /*public int[] twoSum(int[] nums, int target) {
            for (int i = 0; i < nums.length - 1; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] + nums[j] == target){
                        return new int[]{i,j};
                    }
                }
            }
            throw new IllegalArgumentException("No two num solution");
        }*/
        //方式二：时间复杂度0(n)
        public int[] twoSum(int[] nums, int target) {
            Map<Integer,Integer> map = new HashMap<Integer, Integer>(); //<value,index>
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(target - nums[i])){
                    return new int[]{map.get(target - nums[i]),i};
                }
                map.put(nums[i],i);
            }
            throw new IllegalArgumentException("No two num solution");
        }
    }
}
